package com.fanshuai.algorithms.dynamic;

import java.util.List;

/**
 * 背包问题示例
 * 背包问题一般有如下变种：
 * 恰好装满：dp[i][j] 设dp[i][0] = 0, 其他值初始化为-inf。最终查看dp[N][W]是否为-inf
 * 求方案总数：将max换位sum，如0-1背包问题：dp[i][j] = sum(dp[i-1][j], dp[i-1][j-w[j]]), 0<=i<N, w[j]<=j<=W
 * 最小价值：将max换成min
 * 二维背包：背包重量有2个维度dp[i][j1][j2]
 *
 */
public class BagExample {
    /**
     * 分隔等和子集
     * 给定一个只包含正整数的非空数组。问是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * 由于所有元素的和sum已知，所以两个子集的和都应该是sum/2（所以前提是sum不能是奇数），即题目转换成从这个数组里面选取一些元素使这些元素和为sum/2。
     * 如果我们将所有元素的值看做是物品的重量，每件物品价值都为1，所以这就是一个恰好装满的01背包问题。
     */
    public static boolean canPartition(int[] a) {
        int sum = sum(a);
        if (sum % 2 != 0) {
            return false;
        }

        int W = sum / 2; //恰好装满的0-1背包问题
        int len = a.length;
        int[][] dp = new int[len + 1][W + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 0; //重量为0的背包价值为0
            for (int j = 1; j <= W; j++) {
                dp[i][j] = Integer.MIN_VALUE; //恰好装满的0-1背包，初始化为-inf
            }
        }

        /**
         * dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]]) j>=w[i]
         */
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= W; j++) {
                int notChoosed = dp[i - 1][j];
                int choosed = Integer.MIN_VALUE;
                if (j >= a[i - 1]) {
                    choosed = dp[i - 1][j - a[i - 1]] + 1;
                }

                dp[i][j] = Math.max(notChoosed, choosed);
                //System.out.println(String.format("i=%d, j=%d, v=%d", i, j, dp[i][j]));
            }
        }

        return dp[len][W] > 0;
    }

    private static int sum(int[] a) {
        int sum = 0;
        for (int i : a) {
            sum += i;
        }
        return sum;
    }

    private static int add(int x, int y) {
        if (x == Integer.MIN_VALUE || y == Integer.MIN_VALUE) { //-inf
            return Integer.MIN_VALUE;
        }
        if (x == Integer.MAX_VALUE || y == Integer.MAX_VALUE) { //inf
            return Integer.MAX_VALUE;
        }

        return x + y;
    }

    /**
     * 硬币兑换问题
     * 给定一个价值amount和一些面值，假设每个面值的硬币数都是无限的，问我们最少能用几个硬币组成给定的价值。
     * 将面值看作是物品，面值金额看成是物品的重量，每件物品的价值均为1，这样此题就是是一个恰好装满的完全背包问题了。词问题求最少，将max换成min
     *
     * dp[i][j]表示将前i个硬币兑换（每个硬币兑换0次或无限次），价值为amount的最少硬币数量。
     * dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]] + 1)  0<=i<=n, coins[i]<=j<=amount
     */
    public static int coinChange(int[] coins, int amount) {
        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];

        for (int i = 0; i <= len; i++) {
            dp[i][0] = 0;
            for (int j = 1; j <= amount; j++) {
                dp[i][j] = Integer.MAX_VALUE; //求最小值，用inf
            }
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= amount; j++) {
                int notChoosed = dp[i - 1][j];
                int choosed = Integer.MAX_VALUE;

                if (j >= coins[i - 1]) {
                    choosed = dp[i][j - coins[i - 1]] + 1; //完全背包问题
                }
                dp[i][j] = Math.min(notChoosed, choosed);
                //System.out.println(String.format("i=%d, j=%d, v=%d", i, j, dp[i][j]));
            }
        }

        if (dp[len][amount] < Integer.MAX_VALUE) {
            return dp[len][amount];
        } else {
            return -1;
        }
    }

    /**
     * 字符串0和1问题
     * 给定一个仅包含 0 和 1 字符串的数组。任务是从数组中选取尽可能多的字符串，使这些字符串包含的0和1的数目分别不超过m和n。
     * 把每个字符串看做是一件物品，把字符串中0的数目和1的数目看做是两种“重量”，所以就变成了一个二维01背包问题，
     * 书包的两个限重分别是 m 和 n，要求书包能装下的物品的最大数目
     *
     * dp[i][j1][j2] = max(dp[i-1][j1][j2], dp[i-1][j1-w[i]][j2-w[i]] + 1), j1>=w[i], j2>=w[i]
     */
    public static int findMaxForm(String[] sArr, int m, int n) {
        if (null == sArr || sArr.length == 0) {
            return 0;
        }

        int[][] dp = new int[m + 1][n + 1];
        for (String s : sArr) {
            int w0 = 0, w1 = 0;  //0和1字符串重量
            for (char c : s.toCharArray()) {
                if (c == '0') {
                    w0 += 1;
                }
                if (c == '1') {
                    w1 += 1;
                }
            }

            for (int j = m; j >= w0; j--) {
                for (int k = n; k >= w1; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - w0][k - w1] + 1);
                }
            }
        }

        return dp[m][n];
    }

    /**
     * 目标和问题
     * 一个数组（元素非负），和一个目标值，要求给数组中每个数字前添加正号或负号所组成的表达式结果与目标值S相等，求有多少种情况。
     *
     * 设数组为a，a[i]>=0，0<=i<a.length
     * 在数组a的若干位置添加正号，其余位置添加负号。假设添加正号位置的元素和为A，添加负号位置的数组元素和为B(数组原先元素的和，B>0)，设数组a的元素和为sum
     *,有：sum=A+B, S=A-B, 则A = (sum + S) /2。
     * 此问题转换为恰好装满的0-1背包问题：在若干位置选取元素，和为(sum+S)/2。其余位置元素取负号
     *
     * 此问题求解多少方案，因此dp[i][j]表示前i个数据（每个数据选择0或1）的为j的方案数
     *
     * dp[i][0]=1 //和为0的方案数为1（前i个元素都不取）
     * dp[0][j]=0 //前0个元素的和为j的方案数为0
     *
     * dp[i][j] = sum(dp[i-1][j] + dp[i-1][j - a[i]]) j >= a[i]
     */
    public static int targetSum(int[] a, int target) {
        int len = a.length;
        int sum = sum(a);

        if (target > sum || target < -sum) {
            return 0;
        }
        int targetPositive = (sum + target);
        if (targetPositive % 2 == 1) {
            return 0;
        }
        targetPositive = targetPositive / 2;

        int[][] dp = new int[len + 1][targetPositive + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j <= targetPositive; j++) {
            dp[0][j] = 0;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= targetPositive; j++) {
                int notChoosed = dp[i - 1][j];

                int choosed = 0;
                if (j >= a[i - 1]) {
                    choosed = dp[i - 1][j - a[i - 1]];
                }
                dp[i][j] = notChoosed + choosed;
            }
        }

        return dp[len][targetPositive];
    }

    public static void main(String[] args) {
//        int[] a = {1, 3, 5, 2, 4, 6, 3};
//        int[] a2 = {1, 3, 5, 2, 4, 6, 3, 2};
//        System.out.println(canPartition(a));
//        System.out.println(canPartition(a2));
//
//        int[] coins = {1, 2, 5};
//        System.out.println(coinChange(coins, 11));
//        System.out.println(coinChange(coins, 21));
//        System.out.println(coinChange(coins, 22));
//        System.out.println(coinChange(coins, 23));
//        System.out.println(coinChange(coins, 24));

//        int[] a3 = {1, 2, 3, 4};
//        System.out.println(targetSum(a3, 6));
//        System.out.println(targetSum(a3, 4));
//        System.out.println(targetSum(a3, 2));
//        System.out.println(targetSum(a3, 8));
//        System.out.println(targetSum(a3, -2));

        String[] s = {"0101", "1000", "1010"};
        System.out.println(findMaxForm(s, 5, 4));
        System.out.println(findMaxForm(s, 5, 3));
        System.out.println(findMaxForm(s, 5, 2));
    }
}
